package com.leetcode.根据数据结构分类.数组;

import java.util.Arrays;

/**
 * @author: ZhouBert
 * @date: 2021/3/3
 * @description: 338. 比特位计数
 * https://leetcode-cn.com/problems/counting-bits/
 */
public class B_338_比特位计数 {

	static B_338_比特位计数 action = new B_338_比特位计数();

	public static void main(String[] args) {
//		test1();
		test2();
	}

	public static void test1() {
		// [0, 1, 1]
		int num = 2;
		int[] res = action.countBits(num);
		System.out.println(Arrays.toString(res));
	}

	public static void test2() {
		// [0, 1, 1]
		int num = 8;
		int[] res = action.countBits(num);
		System.out.println(Arrays.toString(res));
	}

	/**
	 * 发现规律：当 当前位数 == 1 的个数时，下一个就会导致：
	 * 当前位数+1，1 的个数变为1-- 不对这个规律是有问题的。
	 * --
	 * 看看二进制的特性：
	 * +1：多1个1
	 * +2：多2个1
	 * +4：多3个1
	 * +8：多4个1
	 * 这感觉有点像状态机
	 * 但是我这个方法似乎有点复杂了
	 * 然后一模拟，又不太好模拟这种规律；
	 * --
	 * 最后TMD 看了题解才明白规律：
	 * i 为
	 * 奇数时：res[i] = res[i-1]+1
	 * 偶数时：res[i] = res[i>>1]
	 * 高手，这样就好写了！
	 *
	 * @param num
	 * @return
	 */
	public int[] countBits(int num) {
		int len = num + 1;
		int[] res = new int[len];
		res[0] = 0;
		if (num < 1) {
			return res;
		}
		for (int i = 1; i < len; i++) {
			if ((i & 1) == 0) {
				//偶数
				res[i] = res[i >> 1];
			} else {
				res[i] = res[i - 1] + 1;
			}
		}

		return res;
	}
}
